package hot_100;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class 课程表 {
    public static void main(String[] args) {

        int[][] prerequisites = {{1, 0}};
        boolean ans = canFinish(2, prerequisites);
        System.out.println(ans);
    }

    static int[] ru = new int[2010];
    static int[] head = new int[2010];
    static int[] ed = new int[5010];
    static int[] fa = new int[5010];
    static int cnt = 0;

    public static void add(int x, int y) {
        ed[cnt] = y;
        fa[cnt] = head[x];
        head[x] = cnt++;
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        Arrays.fill(head, -1);
        for (int[] ints : prerequisites) {
            add(ints[1], ints[0]);
            ru[ints[0]]++;
        }
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (ru[i] == 0)
                deque.addFirst(i);
        }
        while (!deque.isEmpty()) {
            Integer x = deque.pollLast();
            numCourses--;
            for (int i = head[x]; i != -1; i = fa[i]) {
                int to = ed[i];
                ru[to]--;
                if (ru[to] == 0)
                    deque.addFirst(to);
            }
        }
        return numCourses == 0;
    }
}
